package com.Offer;

/*
    面试题15：二进制中的1的个数
    题目描述：输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
 */
public class demo15 {
    public static void main(String[] args) {
        System.out.println(NumberOf1(11));
    }

    //思路：每个数都至少有一个1，然后将n减去1之后，如果最右边的1是最后一位，则直接取反，其他位不变
    //如果最右边的1不是最后一位，而是最后一位的前面，则将那一位变为0，后面变为1
    //例如：1100，最后1在从右往左第二位上，则减1之后变为1011，再把1011和1100做与运算得到1000正好是减掉1的个数的结果
    public static int NumberOf1(int n){
        int count = 0;
        while(n != 0){
            count++;
            n = (n-1) & n;
        }
        return count;
    }
}
